package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: Dempsey
 * @Data: 2021-03-15 23:21:55
 */

//中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。 
//
// 找到所有长度为 n 的中心对称数。 
//
// 示例 : 
//
// 输入:  n = 2
//输出: ["11","69","88","96"]
// 
// Related Topics 递归 数学 
// 👍 56 👎 0


public class P247 {
    public static void main(String[] args) {
        Solution solution = new P247().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> findStrobogrammatic(int n) {

            return helper(n, n);

        }

        // n表示，当前循环中，求得字符串长度； m表示题目中要求的字符串长度
        List<String> helper(int n, int m) {
            // 第二步：判断递归是否应当结束
            if (n == 0)
                return new ArrayList<>(Arrays.asList(""));
            if (n == 1)
                return new ArrayList<>(Arrays.asList("0", "1", "8"));

            // 第三步：缩小问题规模
            List<String> list = helper(n - 2, m);

            // 第四步：整合结果
            List<String> res = new ArrayList<>();
            for (String s : list) {
                if (n != m)
                    // n=m时，表示最外层处理。
                    // 例如：原始需求n=m=2, '00'不合法
                    // 若原始需求n=m=4, 内层循环n=2,m=4,'00';最外层循环，n=m=4时，'1001'
                    res.add("0" + s + "0");
                res.add("1" + s + "1");
                res.add("6" + s + "9");
                res.add("8" + s + "8");
                res.add("9" + s + "6");
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}